/*
 * @lc app=leetcode.cn id=227 lang=javascript
 *
 * [227] 基本计算器 II
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  function calc(nums, ops) {
    if (nums.length < 2) return;
    if (ops.length === 0) return;

    let b = nums.pop();
    let a = nums.pop();
    let op = ops.pop();
    let result = 0;

    if (op === '+') {
      result = a + b;
    } else if (op === '-') {
      result = a - b;
    } else if (op === '*') {
      result = a * b;
    } else if (op === '/') {
      result = (a / b) >> 0;
    }

    nums.push(result);
  }
  // 运算符优先级
  const priority = new Map();
  priority.set('$', -1);
  priority.set('+', 1);
  priority.set('-', 1);
  priority.set('*', 2);
  priority.set('/', 2);

  s = s.replace(/\s/g, '');
  // 处理括号内第一位是负数的情况
  s = s.replace('(-', '(0-');
  // 处理最后一位计算问题
  s = s + '$';

  let n = s.length;
  // 加上0为了处理第一位是负数的情况
  const numsStack = [0];
  const opsStack = [];
  for (let i = 0; i < n; i++) {
    let char = s[i];
    if (char === '(') {
      opsStack.push(char);
    } else if (char === ')') {
      // 计算到上一个'('
      while (opsStack.length) {
        if (opsStack[opsStack.length - 1] !== '(') {
          calc(numsStack, opsStack);
        } else {
          opsStack.pop();
          break;
        }
      }
    } else {
      if (/\d/.test(char)) {
        let num = 0;
        let j = i;
        while (j < n && /\d/.test(s[j])) {
          num = num * 10 + Number(s[j++]);
        }
        numsStack.push(num);
        i = j - 1;
      } else {
        while (opsStack.length && opsStack[opsStack.length - 1] !== '(') {
          // 如果当前栈内的符号优先级高，先计算栈内元素
          let prev = opsStack[opsStack.length - 1];
          if (priority.get(prev) >= priority.get(char)) {
            calc(numsStack, opsStack);
          } else {
            break;
          }
        }
        opsStack.push(char);
      }
    }
  }

  // while (opsStack.length) calc(numsStack, opsStack);
  return numsStack[numsStack.length - 1];
};
// @lc code=end
